/**
 * 功能：
 * 作者：lc
 * 日期：2024/9/16 11:13
 */
public class Algorithm_001_SelectBubbleInsert {
    public static void main(String[] args) {
        int[] arr = {6, 2, 5, 3, 4, 7};
        insertOnSort(arr);
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 选择排序
    public static void selectOnSort(int[] arr) {
        // 考虑数组长度为不足2
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int minIndex, i = 0; i < arr.length - 1; i++) {
            // i~n-1,找到最小值，放到i位置
            // 0~n-1
            // 1~n~1 ...
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }

    }

    // 冒泡排序
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 0~n-1
        // 0~n-2
        //...
        //0~1
        for (int end = arr.length - 1; end > 0; end--) {
            //0~end
            //0 1
            //1 2
            //2 3
            // ...
            //end-1 end
            for (int i = 0; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }
//     插入排序
    public static void insertOnSort(int[] arr){
        if (arr == null || arr.length < 2) {
            return;
        }
        /**
         *   for (int i=0;i<arr.length-1;i++){
         *             for (int j=i+1;j>=1;j--){
         *                 if (arr[j]<arr[j-1]){
         *                     swap(arr,j,j-1);
         *                 }
         *             }
         *         }
         */
        for (int i=1;i<arr.length;i++){
            for (int j=i-1;j>=0&&arr[j]>arr[j+1];j--){
                swap(arr,j,j+1);
            }
        }
        for (int a :
                arr) {
            System.out.print(a);
        }
    }
}
